UVa/11842 - Flatland/11842.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 #define DEBUG false
  28 #define dprintf DEBUG and printf
  29 #define dcout DEBUG and cout
  30
  31 inline int cmp(double x, double y = 0, double tol = 1e-9) {
  32     return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  33 }
  34
  35 int Width, Height;
  36
  37 struct Vector {
  38     double x, y;
  39     Vector() {}
  40     Vector(double X, double Y) : x(X), y(Y) {}
  41     inline void normalize() {
  42         double length = sqrt(x * x + y * y);
  43         x /= length; y /= length;
  44     }
  45     bool operator < (const Vector &o) const {
  46         if (cmp(x, o.x) != 0) return cmp(x, o.x) < 0;
  47         return cmp(y, o.y) < 0;
  48     }
  49     bool operator == (const Vector &o) const {
  50         return (cmp(x, o.x) == 0 and
  51                 cmp(y, o.y) == 0);
  52     }
  53 };
  54
  55 struct Person {
  56     double x, y;
  57     Vector d;
  58     string name;
  59
  60     Person(){}
  61     Person(double X, double Y, const Vector &D, string Name) : x(X), y(Y), d(D.x, D.y), name(Name) {}
  62
  63     bool operator < (const Person &o) { return name < o.name; }
  64
  65     double timeToFall() const;
  66
  67     friend ostream &operator<<(ostream &stream, const Person &p);
  68 };
  69
  70 double Person::timeToFall() const {
  71     double horizontal = cmp(this->d.x, 0) < 0 ? this->x / (-this->d.x) : (Width - this->x) / (this->d.x);
  72     double vertical   = cmp(this->d.y, 0) < 0 ? this->y / (-this->d.y) : (Height - this->y) / (this->d.y);
  73     return min(horizontal, vertical);
  74 }
  75
  76 ostream &operator<<(ostream &stream, const Person &p) {
  77     stream << p.name << " is at (" << p.x << ", " << p.y << ") moving in direction <" << p.d.x << ", " << p.d.y << "> (Might fall in " << p.timeToFall() << " seconds)";
  78     return stream;
  79 }
  80
  81 struct Event {
  82     int type; // 0 = free fall, 1 = collision
  83     double time;
  84     Vector point; // point of collision, if any
  85     vector<int> people; // the guy who fell or the two fellows that collided (contains indexes)
  86     string name;
  87
  88     bool operator < (const Event &o) const {
  89         if (cmp(time, o.time) != 0) return cmp(time, o.time) < 0;
  90         if (type != o.type) return type < o.type;
  91         if (type == 0) return name < o.name;
  92         return point < o.point;
  93     }
  94 };
  95
  96 double dot(const Vector &a, const Vector &b) {
  97     return a.x * b.x + a.y * b.y;
  98 }
  99
 100 bool outsideWorld(double x, double y) {
 101     if (cmp(x, 0) < 0) return true;
 102     if (cmp(x, Width) > 0) return true;
 103     if (cmp(y, 0) < 0) return true;
 104     if (cmp(y, Height) > 0) return true;
 105     return false;
 106 }
 107
 108 // Returns the time where person A and B would collide, or -1 if they won't.
 109 double timeOfCollision(const Person &a, const Person &b, Vector &pointOfCollision) {
 110     if (cmp(a.x, b.x) == 0 and cmp(a.y, b.y) == 0) return -1; // They are on the same point, won't collide.
 111
 112     double x0 = a.x, x1 = a.x + a.d.x;
 113     double y0 = a.y, y1 = a.y + a.d.y;
 114
 115     double x2 = b.x, x3 = b.x + b.d.x;
 116     double y2 = b.y, y3 = b.y + b.d.y;
 117
 118     double t0 = (y3-y2)*(x0-x2)-(x3-x2)*(y0-y2);
 119     double t1 = (x1-x0)*(y2-y0)-(y1-y0)*(x2-x0);
 120     double det = (y1-y0)*(x3-x2)-(y3-y2)*(x1-x0);
 121
 122     if (cmp(det, 0) == 0){
 123       //parallel
 124         if (cmp(t0, 0) == 0 || cmp(t1, 0) == 0) {
 125           // they lie on same line. But they might not collide (if they travel in the same direction)
 126             if (cmp(dot(a.d, b.d), 1) == 0) { // They travel in the same direction
 127                 return -1;
 128             }
 129             pointOfCollision.x = x0 + (x2 - x0) / 2;
 130             pointOfCollision.y = y0 + (y2 - y0) / 2;
 131             double dist = hypot(x2 - x0, y2 - y0) / 2;
 132             if (cmp(x0 + dist * a.d.x, pointOfCollision.x) != 0 or cmp(y0 + dist * a.d.y, pointOfCollision.y) != 0 or
 133                 cmp(x2 + dist * b.d.x, pointOfCollision.x) != 0 or cmp(y2 + dist * b.d.y, pointOfCollision.y) != 0) {
 134                 // they travel in opposite directions, but after traveling half the distance they haven't collided, so they'll never collide
 135                     return -1;
 136             }
 137             return dist; // they'll collide in half their distance because they travel in opposite directions
 138         }
 139         //just parallel, no intersection
 140         return -1;
 141     }
 142
 143     t0 /= det;
 144     t1 /= det;
 145
 146     if (cmp(t0, t1) == 0 and cmp(0.0, t0) <= 0 and cmp(0.0, t1) <= 0){
 147         double x = x0 + t0*(x1-x0);
 148         double y = y0 + t0*(y1-y0);
 149         if (outsideWorld(x, y)) return -1;
 150         pointOfCollision.x = x;
 151         pointOfCollision.y = y;
 152         return t0;
 153     }
 154     return -1;
 155 }
 156
 157 int main(){
 158     int Cases; cin >> Cases;
 159     while (Cases--) {
 160         dprintf("Begin case:\n");
 161         int n; cin >> n;
 162         cin >> Width >> Height;
 163
 164         vector<Person> people;
 165         for (int i = 0; i < n; ++i) {
 166             Person p;
 167             cin >> p.x >> p.y >> p.d.x >> p.d.y >> p.name;
 168             p.d.x -= p.x; p.d.y -= p.y; p.d.normalize();
 169             people.push_back(p);
 170             dcout << p << endl;
 171         }
 172
 173         double timeOfLastDeath = -1;
 174         string lastToDie = "";
 175         while (people.size() > 0) {
 176             vector< Event > events;
 177
 178             for (int i = 0; i < people.size(); ++i) {
 179                 Event fall;
 180                 fall.type = 0;
 181                 fall.time = people[i].timeToFall();
 182                 fall.people.push_back(i);
 183                 fall.name = people[i].name;
 184                 events.push_back(fall);
 185
 186
 187                 for (int j = i + 1; j < people.size(); ++j) {
 188                     Person a = people[i], b = people[j];
 189                     Vector point;
 190                     double t = timeOfCollision(a, b, point);
 191
 192                     if (t < 0) {
 193                         //printf("%s and %s won't collide\n", a.name.c_str(), b.name.c_str());
 194                     } else {
 195                         Event collision;
 196                         collision.type = 1;
 197                         collision.time = t;
 198                         collision.point = point;
 199                         collision.people.push_back(i); collision.people.push_back(j);
 200                         events.push_back(collision);
 201                         dprintf("%s and %s could collide at <%lf, %lf> in %lf seconds\n", a.name.c_str(), b.name.c_str(), point.x, point.y, t);
 202                     }
 203                 }
 204             }
 205
 206             assert(events.size() > 0);
 207             sort(events.begin(), events.end());
 208
 209             if (events[0].type == 0) { // free fall, just remove this guy and try again
 210                 if (cmp(events[0].time, timeOfLastDeath) > 0 or cmp(events[0].time, timeOfLastDeath) == 0 and people[events[0].people[0]].name > lastToDie ) {
 211                     lastToDie = people[events[0].people[0]].name;
 212                     timeOfLastDeath = events[0].time;
 213                 }
 214                 people.erase(people.begin() + events[0].people[0]);
 215                 dprintf("%s just fell of at time %lf.\n", lastToDie.c_str(), events[0].time);
 216                 dprintf("Remaining people are:\n");
 217                 for (int i = 0; i < people.size(); ++i){
 218                     dcout << "      " << people[i] << endl;
 219                 }
 220                 continue;
 221             } else {
 222                 double timeOfCollision = events[0].time;
 223                 Vector pointOfCollision = events[0].point;
 224                 set< int > peopleWhoCollided;
 225                 for (int i = 0;  i < events.size() and cmp(events[i].time, timeOfCollision) == 0 and events[i].point == pointOfCollision; i++) {
 226                     peopleWhoCollided.insert(events[i].people.begin(), events[i].people.end());
 227                 }
 228                 dprintf("%d people just collided! Holy bananas!\n", (int)peopleWhoCollided.size());
 229                 if (peopleWhoCollided.size() == 2) { // nothing serious, just swap their directions and try again
 230                     int a = *peopleWhoCollided.begin(), b = *(--peopleWhoCollided.end());
 231                     double dist = hypot(pointOfCollision.x - people[a].x, pointOfCollision.y - people[a].y);
 232                     assert(cmp(dist, hypot(pointOfCollision.x - people[b].x, pointOfCollision.y - people[b].y)) == 0);
 233                     for (int i = 0; i < people.size(); ++i){
 234                         people[i].x += dist * people[i].d.x;
 235                         people[i].y += dist * people[i].d.y;
 236                     }
 237                     swap(people[a].d, people[b].d);
 238                     dprintf("Swapped direction between %s and %s\n", people[a].name.c_str(), people[b].name.c_str());
 239                     dprintf("Remaining people are:\n");
 240                     for (int i = 0; i < people.size(); ++i){
 241                         dcout << "      " << people[i] << endl;
 242                     }
 243                     continue;
 244                 } else {
 245                     // delete those guys who collided
 246                     vector< Person > newPeople;
 247                     for (int i = 0; i < people.size(); ++i) {
 248                         if (peopleWhoCollided.count(i) > 0) {
 249                             if (cmp(events[0].time, timeOfLastDeath) > 0 or cmp(events[0].time, timeOfLastDeath) == 0 and people[i].name > lastToDie ) {
 250                                 lastToDie = people[i].name;
 251                                 timeOfLastDeath = events[0].time;
 252                             }
 253                             dprintf("   %s died in the collision.\n", people[i].name.c_str());
 254                         } else {
 255                             newPeople.push_back(people[i]);
 256                         }
 257                     }
 258                     people = newPeople;
 259                     dprintf("Remaining people are:\n");
 260                     for (int i = 0; i < people.size(); ++i){
 261                         dcout << "      " << people[i] << endl;
 262                     }
 263
 264                     continue;
 265                 }
 266             }
 267
 268
 269
 270             break;
 271         }
 272         assert(lastToDie.size() > 0);
 273         cout << lastToDie << endl;
 274     }
 275     return 0;
 276 }